package pt.ipbeja.estig.eda;

public class QuickSort
{
   int[] array;
   
   /**
    * Quick Sort Constructor
    * @param array Number list
    */
   public QuickSort( int[] array )
   {
      this.array = array;
   }
   
   /**
    * Quick Sort Method
    * @param p Array index
    * @param r Array index
    */
   public void sort( int p, int r )
   {
      if ( p < r )
      {
         int q = partition( p, r );
         sort( p, q - 1 );
         sort( q + 1, r );
      }
   }

   /**
    * Quick Short Partition Method
    * @param p Array index 
    * @param r Array index
    * @return Partition index
    */
   private int partition( int p, int r )
   {
      int x = this.array[ r ];
      int i = p - 1;

      for( int j = p; j <= r - 1; j++ )
      {
         if( this.array[ j ] <= x )
         {
            i++;
            int aux = this.array[ i ];
            this.array[ i ] = this.array[ j ];
            this.array[ j ] = aux;
         }
      }

      int aux = this.array[ i + 1 ];
      this.array[ i + 1 ] = this.array[ r ];
      this.array[ r ] = aux;
      return i + 1;
   }
}